{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Triangle Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: triangleNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效三角形的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含非负整数的数组&nbsp;<code>nums</code> ，返回其中可以组成三角形三条边的三元组个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [2,2,3,4]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>有效的组合是: \n",
    "2,3,4 (使用第一个 2)\n",
    "2,3,4 (使用第二个 2)\n",
    "2,2,3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,2,3,4]\n",
    "<strong>输出:</strong> 4</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-triangle-number](https://leetcode.cn/problems/valid-triangle-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-triangle-number](https://leetcode.cn/problems/valid-triangle-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,4]', '[4,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                left, right, k = j + 1, n - 1, j\n",
    "                while left <= right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if nums[mid] < nums[i] + nums[j]:\n",
    "                        k = mid\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "                ans += k - j\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        def bin_search(lo, hi, t):\n",
    "            if lo == hi:\n",
    "                return lo\n",
    "            m = (lo + hi) // 2\n",
    "            if nums[m] < t:\n",
    "                return bin_search(m + 1, hi, t)\n",
    "            else:\n",
    "                return bin_search(lo, m, t)\n",
    "        \n",
    "        #nums = sorted(nums)\n",
    "        nums=[x for x in nums if x > 0]\n",
    "        nums=sorted(nums)\n",
    "        #ret = []\n",
    "        ret=0\n",
    "        t = 0\n",
    "        for a in range(len(nums) - 2):\n",
    "            t = nums[a]\n",
    "            c = a + 2\n",
    "            for b in range(a + 1, len(nums) - 1):\n",
    "                t += nums[b]\n",
    "                c = bin_search(c, len(nums), t)\n",
    "                ret += c-b-1\n",
    "                #ret.append((a,b,c))\n",
    "                t -= nums[b]\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        def is_valid(arr):\n",
    "            arr = sorted(arr)\n",
    "            return (arr[0] + arr[1]) > arr[2]\n",
    "        def solve(index,temp):\n",
    "\n",
    "            if len(temp) == 3 and is_valid(temp):\n",
    "                nonlocal res\n",
    "                res += 1\n",
    "                return\n",
    "            if index >= len(nums):\n",
    "                return\n",
    "            # take\n",
    "            temp.append(nums[index])\n",
    "            solve(index + 1, temp)\n",
    "            temp.pop()\n",
    "            # not take\n",
    "            solve(index + 1, temp)\n",
    "       \n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                a = nums[i]\n",
    "                b = nums[j]\n",
    "                start = j + 1\n",
    "                end = len(nums) - 1\n",
    "                while start <= end:\n",
    "                    mid = (start + end) // 2\n",
    "                    if nums[mid] < a + b:\n",
    "                        start = mid + 1\n",
    "                    elif nums[mid] == a + b:\n",
    "                        end = mid - 1\n",
    "                    elif nums[mid] > a + b:\n",
    "                        end = mid - 1\n",
    "                if end >= j and a + b > nums[end]:\n",
    "                    res += end - j\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        \n",
    "        dir = {}\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                count += 1\n",
    "                if num not in dir:\n",
    "                    dir[num] = 1\n",
    "                else:\n",
    "                    dir[num] += 1\n",
    "\n",
    "        List = list(dir.keys())\n",
    "        List.sort()\n",
    "\n",
    "        record = {}\n",
    "\n",
    "        for num in List[:-1]:\n",
    "            ans  = dir[num]*(dir[num]-1)//2\n",
    "            if ans:\n",
    "                record[num*2] = ans\n",
    "\n",
    "        k = len(List)\n",
    "\n",
    "        for i in range(0,k-1):\n",
    "            for j in range(i+1,k):\n",
    "                a,b = List[i],List[j]\n",
    "                if a+b not in record:\n",
    "                    record[a+b] = dir[a]*dir[b]\n",
    "                else:\n",
    "                    record[a+b] += dir[a]*dir[b]\n",
    "\n",
    "        # print(record)\n",
    "\n",
    "        mount = []\n",
    "        for num in List:\n",
    "            mount.append(dir[num])\n",
    "\n",
    "        # print(mount)\n",
    "\n",
    "        all_sum = sum(mount)\n",
    "\n",
    "        for i in range(k-1):\n",
    "            \n",
    "            tmp = mount[i]\n",
    "            mount[i] = all_sum\n",
    "            all_sum -= tmp\n",
    "        \n",
    "        # print(List)\n",
    "        # print(mount)\n",
    "        # print(dir)\n",
    "        # print(record)\n",
    "\n",
    "        def left_bound(nums,target):\n",
    "            left,right = 0,len(nums)\n",
    "            while left < right:\n",
    "                mid = (left+right)//2\n",
    "                if nums[mid] == target:\n",
    "                    right = mid\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid\n",
    "            return left\n",
    "\n",
    "        res = 0\n",
    "        for r in record:\n",
    "\n",
    "            idx = left_bound(List,r)\n",
    "            if idx < k:\n",
    "                # print('hahaha')\n",
    "                p = mount[idx]\n",
    "                res += p*record[r]\n",
    "        \n",
    "        return count*(count-1)*(count-2)//6 - res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        def find_index(first, second, start, end):\n",
    "            if first + second <= nums[start]:\n",
    "                return None\n",
    "            if first + second > nums[end]:\n",
    "                return end\n",
    "            middle = (start + end) // 2\n",
    "            if nums[middle] < first + second <= nums[middle + 1]:\n",
    "                return middle\n",
    "            if first + second > nums[middle]:\n",
    "                return find_index(first, second, middle, end)\n",
    "            else:\n",
    "                return find_index(first, second, start, middle)\n",
    "        count = 0\n",
    "        for i in range(len(nums) - 2):\n",
    "            for j in range(i + 1, len(nums) - 1, 1):\n",
    "                index = find_index(nums[i], nums[j], j + 1, len(nums)-1)\n",
    "                if index:\n",
    "                    count += index - j\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0 \n",
    "        nums=SortedList(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                ind = nums.bisect_left(nums[i]+nums[j])-1\n",
    "                ans += max(0,(ind-j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            c = nums[i]\n",
    "            l, r = 0, i - 1\n",
    "            while l < r:\n",
    "                a, b = nums[l], nums[r]\n",
    "                if a + b > c:\n",
    "                    res += r - l \n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        s=sortedcontainers.SortedList(nums)\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        sset=dict()\n",
    "        for i in range(len(nums)-2):\n",
    "            for j in range (i+1, len(nums)-1):\n",
    "                adduo=nums[i]+nums[j]-1\n",
    "                if adduo not in sset:\n",
    "                    amount=s.bisect_right(adduo)-1\n",
    "                    sset[adduo]=amount\n",
    "                else:\n",
    "                    amount=sset[adduo]\n",
    "                if amount-j>0:\n",
    "                    ans+=amount-j\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        import bisect\n",
    "        nums.sort()\n",
    "        paths = []\n",
    "        self.r = 0\n",
    "        self.search([], 0, nums)\n",
    "        return self.r\n",
    "    \n",
    "    def search(self, edges, i, nums):\n",
    "        if len(edges) == 3:\n",
    "            self.r += 1\n",
    "            return\n",
    "        n = len(nums)\n",
    "        if i == n:\n",
    "            return\n",
    "        if len(edges) == 0 or len(edges) == 1:\n",
    "            self.search(edges, i + 1, nums)\n",
    "            edges.append(nums[i])\n",
    "            self.search(edges, i + 1, nums)\n",
    "            edges.pop()\n",
    "        else:\n",
    "            x, y = edges\n",
    "            z = x + y\n",
    "            pos = bisect.bisect_left(nums, z)\n",
    "            if pos > i:\n",
    "                self.r += pos - i\n",
    "            # if nums[i] < z:\n",
    "            #     self.search(edges, i + 1, nums)\n",
    "            #     edges.append(nums[i])\n",
    "            #     self.search(edges, i + 1, nums)\n",
    "            #     edges.pop()\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        def isTriangle(arr):\n",
    "            if nums[arr[0]]+nums[arr[1]] > nums[arr[2]]:\n",
    "                return True\n",
    "            return False\n",
    "       \n",
    "        def dfs(index, ret):\n",
    "            if index == 3:\n",
    "                ret.sort()\n",
    "                if isTriangle(ret[:]): \n",
    "                    self.count+=1\n",
    "                return\n",
    "\n",
    "            for i in range(n):\n",
    "                if not visited[i] or (len(ret)>0 and i<=ret[-1]):\n",
    "                    continue\n",
    "                visited[i] = False\n",
    "                dfs(index+1, ret+[i])\n",
    "                visited[i] = True\n",
    "\n",
    "        if not nums or len(nums)<3:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        visited = [True]*n\n",
    "        self.count = 0\n",
    "        nums.sort()\n",
    "        # dfs(0, [])\n",
    "\n",
    "        for i in range(0, n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                sum = nums[i] + nums[j]\n",
    "                left, right, k = j+1, n-1, j\n",
    "                while left<=right:\n",
    "                    mid = (right+left)//2\n",
    "                    if nums[mid]<sum:\n",
    "                        k=mid\n",
    "                        left = mid+1\n",
    "                    else:\n",
    "                        right = mid-1\n",
    "                self.count += k-j\n",
    "\n",
    "        return self.count\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        def bin_search(lo, hi, t):\n",
    "            if lo == hi:\n",
    "                return lo\n",
    "            m = (lo + hi) // 2\n",
    "            if nums[m] == t:\n",
    "                while m > lo and nums[m-1] == t:\n",
    "                    m -= 1\n",
    "                return m\n",
    "            elif nums[m] < t:\n",
    "                return bin_search(m + 1, hi, t)\n",
    "            else:\n",
    "                return bin_search(lo, m, t)\n",
    "        \n",
    "        #nums = sorted(nums)\n",
    "        nums=[x for x in nums if x > 0]\n",
    "        nums=sorted(nums)\n",
    "        #ret = []\n",
    "        ret=0\n",
    "        t = 0\n",
    "        for a in range(len(nums) - 2):\n",
    "            t = nums[a]\n",
    "            c = a + 2\n",
    "            for b in range(a + 1, len(nums) - 1):\n",
    "                t += nums[b]\n",
    "                c = bin_search(c, len(nums), t)\n",
    "                ret += c-b-1\n",
    "                #ret.append((a,b,c))\n",
    "                t -= nums[b]\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        resultNumbers=0\n",
    "        n=len(nums)\n",
    "        self.sortArray(nums)\n",
    "        for i in range(n):\n",
    "            k = i\n",
    "            for j in range(i + 1, n):\n",
    "                while k < n and nums[k] < nums[i] + nums[j]:\n",
    "                    k += 1\n",
    "                resultNumbers += max(k - j - 1, 0)\n",
    "        return resultNumbers\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def randomized_partition(self,nums,l,r):\n",
    "        i=l-1\n",
    "        pivot=randint(l,r-1)\n",
    "        nums[r-1],nums[pivot]=nums[pivot],nums[r-1]\n",
    "        for j in range(l,r-1):\n",
    "            if nums[j] < nums[r-1]:\n",
    "                i=i+1\n",
    "                nums[i],nums[j]=nums[j],nums[i]\n",
    "                \n",
    "        i=i+1\n",
    "        nums[i],nums[r-1]=nums[r-1],nums[i]\n",
    "        return i\n",
    "        \n",
    "    def randomized_quicksort(self, nums, l, r):\n",
    "        if r-l<=1:\n",
    "            return\n",
    "        mid=self.randomized_partition(nums,l,r)\n",
    "        self.randomized_quicksort(nums,l,mid)\n",
    "        self.randomized_quicksort(nums,mid+1,r)\n",
    "\n",
    "\n",
    "\n",
    "    def sortArray(self, nums):\n",
    "        l=0\n",
    "        r=len(nums)\n",
    "        self.randomized_quicksort(nums,l,r)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        #任意两边大于第三边即可\n",
    "        #结合nums排序后状态\n",
    "        #即判断nums[k] + nums[i] > nums[j] 成立即有效三角形\n",
    "        nums.sort()\n",
    "        L =len(nums)\n",
    "        s = 0\n",
    "        for j in range(2, L):\n",
    "            k = 0\n",
    "            i = j - 1\n",
    "            while k < i:\n",
    "                \n",
    "                if nums[k] + nums[i]  > nums[j] :\n",
    "                    s += i - k\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    k += 1\n",
    "        return s\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i,x in enumerate(nums):\n",
    "            if x != 0:\n",
    "                break\n",
    "        nums = nums[i:]\n",
    "        def huisu(wei,pre1,pre2):\n",
    "            if pre1 != -1 and pre2 != -1:\n",
    "                lin = nums[wei:]\n",
    "                left = bisect.bisect_right(lin,pre2-pre1)\n",
    "                right = bisect.bisect_left(lin,pre1+pre2)\n",
    "                return (right-left)\n",
    "            res = 0\n",
    "            for i in range(wei,len(nums)):\n",
    "                if pre1 != -1:\n",
    "                    res += huisu(i+1,pre1,nums[i])\n",
    "                else:\n",
    "                    res += huisu(i+1,nums[i],-1)\n",
    "            return res\n",
    "        return huisu(0,-1,-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        import bisect\n",
    "        nums.sort()\n",
    "        paths = []\n",
    "        self.r = 0\n",
    "        self.search([], 0, nums)\n",
    "        return self.r\n",
    "    \n",
    "    def search(self, edges, i, nums):\n",
    "        if len(edges) == 3:\n",
    "            self.r += 1\n",
    "            return\n",
    "        n = len(nums)\n",
    "        if i == n:\n",
    "            return\n",
    "        if len(edges) == 0 or len(edges) == 1:\n",
    "            self.search(edges, i + 1, nums)\n",
    "            edges.append(nums[i])\n",
    "            self.search(edges, i + 1, nums)\n",
    "            edges.pop()\n",
    "        else:\n",
    "            x, y = edges\n",
    "            z = x + y\n",
    "            pos = bisect.bisect_left(nums, z)\n",
    "            if pos > i:\n",
    "                self.r += pos - i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums) ==0:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(2, len(nums)):\n",
    "            l, r = 0, i - 1\n",
    "\n",
    "            while l < r:\n",
    "                if nums[l] + nums[r] <= nums[i]:\n",
    "                    l +=1\n",
    "                else:\n",
    "                    ans += r-l\n",
    "                    r -= 1\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for index in range(2, len(nums)):\n",
    "            left, right = 0, index - 1\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] <= nums[index]:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans += (right - left)\n",
    "                    right -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i in range(n - 2):\n",
    "            if nums[i] == 0: continue\n",
    "            k = i + 2\n",
    "            for j in range(i + 1, n - 1):\n",
    "                while k < n and nums[i] + nums[j] > nums[k]:\n",
    "                    k += 1\n",
    "                ans += k - j - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            k=i\n",
    "            # for j in range(k+1,n):\n",
    "            for j in range(i+1,n):\n",
    "                while k+1<n and nums[k+1]<nums[i]+nums[j]:\n",
    "                    k+=1\n",
    "                ans+=max(k-j,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        alls=[]\n",
    "        for i in range(n):\n",
    "            k=i\n",
    "            # for j in range(k+1,n):\n",
    "            for j in range(i+1,n):\n",
    "                while k+1<n and nums[k+1]<nums[i]+nums[j]:\n",
    "                    k+=1\n",
    "                # ans+=max(k-j,0)\n",
    "                if k-j>0:\n",
    "                    ans+=k-j\n",
    "                    # for m in range(j+1,k+1):\n",
    "                    #     alls.append([nums[i],nums[j],nums[k]])\n",
    "        # print(alls)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(2,n):\n",
    "            left = 0\n",
    "            right = i -1\n",
    "            while right > left:\n",
    "                if nums[right] + nums[left] > nums[i]:\n",
    "                    res += (right - left)\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums) - 2):\n",
    "            first = nums[i]\n",
    "            k = i\n",
    "            for j in range(i + 1, len(nums) - 1):\n",
    "                second = nums[j]\n",
    "                while k < len(nums) - 1:\n",
    "                    third = nums[k + 1]\n",
    "                    if third < first + second:\n",
    "                        k += 1\n",
    "                    else:\n",
    "                        break\n",
    "                # print(\"j: \", j, \"k: \", k)\n",
    "                res += max(0, k - j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: 'List[int]') -> 'int':\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        # 从大到小遍历\n",
    "        for i in range(len(nums) - 1, 1, -1):\n",
    "            l, r = 0, i -1\n",
    "            while l < r:\n",
    "                # 只要较小的两个值之和大于最大的值，则一定可组成三角形\n",
    "                if nums[l] + nums[r] > nums[i]:\n",
    "                    #i, r 和从l到r-1都可组成三角形，个数为 (r-1) - l + 1 = r - l\n",
    "                    res += (r-1) - l + 1\n",
    "                    r -= 1\n",
    "                else: l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for k in range(2,n):\n",
    "            i = 0\n",
    "            j = k-1\n",
    "            while i<j:\n",
    "                if (nums[i]+nums[j])>nums[k]: #把关系都写为和规律，其中的两个加数作为左右指针，和为常亮或循环变量\n",
    "                # 加数比较多时，其他加数也可以为循环变量，但关系算式必须是相加的关系，指针为和数，在左边   比如：i+j+a+b==target （四数之和问题，i循环，j循环）\n",
    "                    ans =ans+ j-i\n",
    "                    j -= 1\n",
    "                    \n",
    "                else:\n",
    "                    i += 1  \n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                left, right, k = j+1, n-1, j\n",
    "                while left <= right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if nums[mid] < nums[i] + nums[j]:\n",
    "                        k = mid\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "                ans += k-j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        size = len(nums)\n",
    "        if size < 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "\n",
    "        for i in range(2, size):\n",
    "            left, right = 0, i - 1\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] > nums[i]:\n",
    "                    count += (right - left)\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return count \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for k in range(2,len(nums)):\n",
    "            c = nums[k]\n",
    "            i = 0\n",
    "            j = k - 1\n",
    "            while i < j:\n",
    "                if nums[i] + nums[j] > c:\n",
    "                    res += j -i\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for k in range(2,n): # 和两数之和一样，从锚点的左边开始枚举\n",
    "            c= nums[k]\n",
    "            i = 0\n",
    "            j = k-1\n",
    "            while i<j:\n",
    "                if nums[i] + nums[j]>c:\n",
    "                    ans+=j-i\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(2, n):\n",
    "            j = 0\n",
    "            k = i - 1\n",
    "\n",
    "            while j < k:\n",
    "                if nums[i] < nums[j] + nums[k]:\n",
    "                    ans += k - j\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         for k in range(j + 1, n):\n",
    "        #             if nums[i] + nums[j] > nums[k]:\n",
    "        #                 cnt += 1\n",
    "        # return cnt\n",
    "        for i in range(n-1, 1, -1):\n",
    "            l = 0\n",
    "            r = i - 1\n",
    "            while l < r:\n",
    "                if nums[l] + nums[r] > nums[i]:\n",
    "                    cnt += r - l\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "        return cnt\n",
    "                    \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            k = i\n",
    "            for j in range(i+1, n):\n",
    "                while k + 1 < n and nums[k+1] < nums[i] + nums[j]:\n",
    "                    k += 1\n",
    "                count += max(0, k - j)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                # 找第一个>= nums[i] + nums[j]的下标\n",
    "                left, right = j+1, n\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if nums[mid] < nums[i] + nums[j]:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid \n",
    "                res += (left - j - 1)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for k in range(2, len(nums)):\n",
    "            c = nums[k]\n",
    "            i = 0  # a=nums[i]\n",
    "            j = k - 1  # b=nums[j]\n",
    "            while i < j:\n",
    "                if nums[i] + nums[j] > c:\n",
    "                    # 由于 nums 已经从小到大排序\n",
    "                    # nums[i]+nums[j] > c 同时意味着：\n",
    "                    # nums[i+1]+nums[j] > c\n",
    "                    # nums[i+2]+nums[j] > c\n",
    "                    # ...\n",
    "                    # nums[j-1]+nums[j] > c\n",
    "                    # 从 i 到 j-1 一共 j-i 个\n",
    "                    ans += j - i\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    # 由于 nums 已经从小到大排序\n",
    "                    # nums[i]+nums[j] <= c 同时意味着\n",
    "                    # nums[i]+nums[j-1] <= c\n",
    "                    # ...\n",
    "                    # nums[i]+nums[i+1] <= c\n",
    "                    # 所以在后续的循环中，nums[i] 不可能作为三角形的边长，没有用了\n",
    "                    i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = i\n",
    "            for j in range(i + 1, n):\n",
    "                while k + 1 < n and nums[k + 1] < nums[i] + nums[j]:\n",
    "                    k += 1\n",
    "                ans += max(k - j, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for right in range(2, n):\n",
    "            left = 0\n",
    "            mid = right - 1\n",
    "            while left < mid:\n",
    "                if nums[left] + nums[mid] > nums[right]:\n",
    "                    res += mid - left\n",
    "                    mid -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        result, n = 0, len(nums)\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                temp = bisect_left(nums, nums[i]+nums[j])\n",
    "                if temp > j:\n",
    "                    result += (temp - j - 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef triangleNumber(self, nums):\n",
    "\t\ta = sorted(x for x in nums if x > 0)\n",
    "\t\tans = 0\n",
    "\t\tfor i in range(len(a)):\n",
    "\t\t\tfor j in range(i + 1, len(a)):\n",
    "\t\t\t\tx = bisect_left(a, a[j] - a[i] + 1, j + 1)\n",
    "\t\t\t\ty = bisect_left(a, a[i] + a[j], j + 1)\n",
    "\t\t\t\tans += y - x\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                s = nums[i] + nums[j]\n",
    "                left = j + 1\n",
    "                right = n\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if nums[mid] < s:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid\n",
    "                ans = ans + right - (j + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        nums.sort(reverse=True)\n",
    "        i = 0\n",
    "        for i in range(0,n-2):\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            while j<k:\n",
    "                if nums[j] + nums[k] <= nums[i]:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    ans += k-j\n",
    "                    j += 1\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        # def is_triangle(a, b, c):\n",
    "        #     # 对于非递减序列，一定有a + c > b, b + c > a, 只有 a + b > c是未知的 （假设a, b ,c对于的索引号依次递增） \n",
    "        #     if a*b*c == 0:\n",
    "        #         return False\n",
    "        #     return (a + b > c) and (a + c > b) and (b + c > a)\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n-2):\n",
    "            if nums[i] == 0:\n",
    "                continue\n",
    "            for j in range(i+1, n-1):\n",
    "                # 1. 暴力搜索区间[j, n-1], 找到第一个不满足要求的元素值： 时间超时(O(n^3))\n",
    "                # k = j + 1\n",
    "                # while k < n and nums[i] + nums[j] > nums[k]:\n",
    "                #     k += 1\n",
    "                    \n",
    "                # if k < n or nums[i] + nums[j] > nums[-1]: # 若上述循环异常退出\n",
    "                #     count += (k - j - 1)\n",
    "                # 2.二分法搜索区间[j, n-1], 找到第一个不满足要求的元素值\n",
    "                left, right = j + 1, n - 1\n",
    "                while left < right:\n",
    "                    mid = left + (right - left) // 2\n",
    "                    if nums[i] + nums[j] > nums[mid]:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "\n",
    "                if nums[i] + nums[j] > nums[left]:\n",
    "                    tar = left + 1\n",
    "                else:\n",
    "                    tar = left\n",
    "\n",
    "                count += (tar - j - 1)   \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        re = 0\n",
    "        for i in range(l-1,1,-1):\n",
    "            j = 0\n",
    "            k = i-1\n",
    "            while j<k:\n",
    "                if nums[j]+nums[k]>nums[i]:\n",
    "                    re+=k-j\n",
    "                    k-=1\n",
    "                else:\n",
    "                    j+=1\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            k = i\n",
    "            for j in range(i+1,len(nums)):\n",
    "                while k+1<len(nums) and nums[i]+nums[j]>nums[k+1]:\n",
    "                    k += 1\n",
    "                res += max(k-j,0)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n - 1, 1, -1):\n",
    "            left, right = 0, i - 1\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] > nums[i]:\n",
    "                    res += right - left\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(len(nums)-1, 1, -1):\n",
    "            for j in range(i-1, 0, -1):\n",
    "                l, r = 0, j-1\n",
    "                while l < r:\n",
    "                    mid = (l+r)//2\n",
    "                    if nums[mid] + nums[j] <= nums[i]:\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid \n",
    "                if nums[l] + nums[j] > nums[i]:\n",
    "                    res += j-l \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for k in range(2, len(nums)):\n",
    "            c = nums[k]\n",
    "            i = 0  # a=nums[i]\n",
    "            j = k - 1  # b=nums[j]\n",
    "            while i < j:\n",
    "                if nums[i] + nums[j] > c:\n",
    "                    # 由于 nums 已经从小到大排序\n",
    "                    # nums[i]+nums[j] > c 同时意味着：\n",
    "                    # nums[i+1]+nums[j] > c\n",
    "                    # nums[i+2]+nums[j] > c\n",
    "                    # ...\n",
    "                    # nums[j-1]+nums[j] > c\n",
    "                    # 从 i 到 j-1 一共 j-i 个\n",
    "                    ans += j - i\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    # 由于 nums 已经从小到大排序\n",
    "                    # nums[i]+nums[j] <= c 同时意味着\n",
    "                    # nums[i]+nums[j-1] <= c\n",
    "                    # ...\n",
    "                    # nums[i]+nums[i+1] <= c\n",
    "                    # 所以在后续的循环中，nums[i] 不可能作为三角形的边长，没有用了\n",
    "                    i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(2, n):\n",
    "            left, right = 0, i - 1\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] > nums[i]:\n",
    "                    res += right - left\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            l = 0\n",
    "            r = i - 1\n",
    "            while l < r:\n",
    "                if nums[l] + nums[r] > nums[i]:\n",
    "                    ans += r - l\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n-2):\n",
    "            k = i + 2\n",
    "            if nums[i] == 0: continue\n",
    "\n",
    "            for j in range(i+1, n-1):\n",
    "                while k < n and nums[i] + nums[j] > nums[k]:\n",
    "                    k+=1\n",
    "                count += k - j-1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(2, n):\n",
    "            x = nums[i]\n",
    "\n",
    "            l, r = 0, i - 1\n",
    "            while l < r:\n",
    "                sum = nums[r] + nums[l]\n",
    "                if sum > x:\n",
    "                    ans += r - l\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "         \n",
    "        # 三角形三条边\n",
    "        # a + b > c c 最长边\n",
    "        # 倒序遍历\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(n - 1, 1, -1):\n",
    "            x = nums[i]\n",
    "            j = 0\n",
    "            k = i - 1\n",
    "\n",
    "            while j < k:\n",
    "\n",
    "                sum1 = nums[j] + nums[k]\n",
    "                \n",
    "                if sum1 > x:\n",
    "                    res += k - j\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for k in range(2, len(nums)):\n",
    "            c = nums[k]\n",
    "            i = 0\n",
    "            j = k - 1\n",
    "            while i < j:\n",
    "                if nums[i] + nums[j] > c:\n",
    "                    # [i,j] > c\n",
    "                    # [i+1, j] > c\n",
    "                    # [j-1, j] > c\n",
    "                    # 从i 到 j+1 都 > c\n",
    "                    ans += j - i\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    # [i,j] < c\n",
    "                    # [i, j-1] < c\n",
    "                    # [i, i+1] < c\n",
    "                    # i 到 j 都不满足\n",
    "                    i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for k in range(2,n):\n",
    "            i = 0\n",
    "            j = k-1\n",
    "            while i < j:\n",
    "                if nums[i]+nums[j]>nums[k]:\n",
    "                    ans += j-i\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    i += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for c in range(2, len(nums)):\n",
    "            a = 0\n",
    "            b = c - 1\n",
    "            \n",
    "            while a < b:\n",
    "                if nums[a] + nums[b] > nums[c]:\n",
    "                    res += b - a\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    a += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n - 2):\n",
    "            for j in range(i+1, n - 1):\n",
    "                idx = bisect.bisect_left(nums, nums[i] + nums[j])\n",
    "                if idx > j:\n",
    "                    ans += idx - 1 - j\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        number = 0\n",
    "        import bisect\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                index = bisect.bisect_left(nums[j+1:], nums[i]+nums[j])\n",
    "                number += index\n",
    "\n",
    "\n",
    "        return number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            l = 0\n",
    "            r = i - 1\n",
    "            while l < r:\n",
    "                if nums[l] + nums[r] > nums[i]:\n",
    "                    ans += r - l\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n - 2):\n",
    "            if nums[i] == 0:  # 如果固定的较长边为 0，则直接跳过\n",
    "                continue\n",
    "            k = i + 2\n",
    "            for j in range(i + 1, n - 1):\n",
    "                while k < n and nums[i] + nums[j] > nums[k]:\n",
    "                    k += 1\n",
    "                count += max(k - j - 1, 0)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res=0 #满足的个数\n",
    "        for n in range(len(nums)-1,1,-1):\n",
    "        #固定最长边，从后往前取，保证其长度大\n",
    "            l=0#最短边\n",
    "            r=n-1#次长边\n",
    "            while l<r:\n",
    "                if nums[l]+nums[r]>nums[n]:\n",
    "                    res+=(r-l)#都满足结果\n",
    "                    r-=1#次边缩短，直到不满足，就开始l移动\n",
    "                else:\n",
    "                    l+=1#短边增长，找到满足两边之和大于第三边\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        def check(a, b, c):\n",
    "            if a+b <= c or a+c <= b or b+c <= a:\n",
    "                return False\n",
    "            if abs(a-b) >= c or abs(a-c)>=b or abs(b-c) >=a:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        n = nums.__len__()\n",
    "        # m = {}\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i in range(2, n):\n",
    "            left, right = 0, i-1\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] <= nums[i]:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans += (right - left)\n",
    "                    right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        for i in range(n-1,1,-1):\n",
    "            c=nums[i]\n",
    "            left=0\n",
    "            right=i-1\n",
    "            while left<right:\n",
    "                a=nums[left]\n",
    "                b=nums[right]\n",
    "                if a+b>c:\n",
    "                    res+=right-left\n",
    "                    right-=1\n",
    "                else:\n",
    "                    left+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n, result = len(nums), 0\n",
    "        for a in range(n-2):\n",
    "            for c in range(n-1, a+1, -1):\n",
    "                b_range = nums[a+1:c]\n",
    "                b = bisect_right(b_range, nums[c]-nums[a])\n",
    "                result += (len(b_range)-b) \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        #排序 + 双指针\n",
    "        nums.sort()\n",
    "        #定义 a <= b <= c\n",
    "        #则满足题意的条件为 a + b >= c\n",
    "        #逆序枚举最大值\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for k in range(2,n):\n",
    "            c = nums[k]\n",
    "            i = 0\n",
    "            j = k - 1\n",
    "            while i < j:\n",
    "                if nums[i] + nums[j] > c:\n",
    "                    #对于j来说，前面的每一个i都满足\n",
    "                    ans += j - i\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    #nums[i] + nums[j] <= c\n",
    "                    #说明对于i来说，后面的每一个j都不满足构成三角形的条件\n",
    "                    i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                l,r,k = j+1,n-1,j\n",
    "                while l<=r:\n",
    "                    mid = (l+r)//2\n",
    "                    if nums[mid]<nums[i]+nums[j]:\n",
    "                        k = mid\n",
    "                        l = mid+1\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                res += k-j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        size = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(2, size):\n",
    "            left =0\n",
    "            right = i - 1\n",
    "            while left <= right:\n",
    "                if nums[left] + nums[right] <= nums[i]:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans += (right - left)\n",
    "                    right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                left, right, k = j + 1, n - 1, j\n",
    "                while left <= right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if nums[mid] < nums[i] + nums[j]:\n",
    "                        k = mid\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "                ans += k - j\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def triangleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(2,n):\n",
    "            left=0\n",
    "            right=i-1\n",
    "            while left<right:\n",
    "                if nums[left]+nums[right]>nums[i] and nums[i]-nums[right]<nums[left]:\n",
    "                    ans+=right-left\n",
    "                    right-=1\n",
    "                else:\n",
    "                    left+=1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
